home *** CD-ROM | disk | FTP | other *** search
/ Info-Mac 11 / Info-Mac_XI_Disc_1.cdr_ / Info-Mac XI Disc 1.cdr / Programs / Science & Math / MacEspresso 1.0 / espresso / essentiality.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-12-10  |  7.9 KB  |  346 lines  |  [TEXT/R*ch]
  1. /*
  2. /* Module:essentiality.c
  3.  *    contains routines for performing essentiality test and reduction
  4.  * Routines:
  5.  * pcover ess_test_and_reduction():
  6.  *    determines essentiality of the given signature cube and returns
  7.  *     cover of the signature cube (Hammered signature cube) if found
  8.  *    inessential.    
  9.  * pcover aux_ess_test_and_reduction():
  10.  *    core compuation routine which determines the essentiality of
  11.  *    the signature cube and performs reduction of inessential signature
  12.  *    cubes by recursively descending down the cube-tree.
  13.  */
  14.  
  15.  
  16.  
  17. #include <stdio.h>
  18. #include "espresso.h"
  19. #include "signature.h"
  20.  
  21. /* Yuk, Yuk, Yuk!! More Globals. It seems recursive routines have unholy
  22.    alliance with globals */
  23.  
  24. static int *c_free_list; /* List of raised variables  in cube c */
  25. static int c_free_count; /* active size of the above list */
  26.  
  27. static int *r_free_list; /* List of subset of raised variables in cube c
  28.             which are raised in each cube of offset R */
  29. static int r_free_count; /* active size of the above list */
  30. static int r_head; /* current position in  the list above */
  31.  
  32. static int *reduced_c_free_list; /* c_free_list - r_free_list */
  33. static int reduced_c_free_count; /* active size of the above list */
  34.  
  35. typedef struct {
  36.     int variable;
  37.     int free_count;
  38.     } VAR;
  39.  
  40. static VAR *unate_list; /* List of unate variables in the reduced_c_free_list */
  41. static int unate_count; /* active size of the above list */
  42.  
  43. static VAR *binate_list; /* List of binate variables in the 
  44.              reduced_c_free_list */
  45. static int binate_count; /* active size of the above list */
  46.  
  47. static int *variable_order; /* permutation of reduced c_free_count determining 
  48.                 static ordering of variables */
  49. static int variable_count; /* active size of the above list */
  50. static int variable_head; /* current position in  the list above */
  51.  
  52. /* The passive size allocated on the first call to etr_order is equal
  53.    to the number of binary variables */
  54. /* Clearly not the most optimized usage of memory. Not worth saving
  55.    few pennies when the total memory budget is quite large */
  56.  
  57. pcover COVER; /* A global bag to collect the signature cubes in the cover 
  58.          of inessential signature cube */
  59.  
  60. /* etr_order:
  61.  * What does it do:
  62.  *    Performs performs ordering of variables before calling
  63.  *    essentiality test and reduction routine 
  64.  * Inputs:
  65.  *    R: Cover of the Off-set.
  66.  *    c: cube to be reduced
  67.  * Output:
  68.  *    COVER: signature cube cover of given inessential signature cube
  69.  * Strategy: As many cubes in the cover as possible.
  70.  *     -> As deep a search tree recursion as possible
  71.  *    -> variable ordering
  72.  *    -> static ordering to minimize computation
  73.  *        1. Free
  74.  *        2. Freer Unate
  75.  *        3. Freer Binate
  76.  */
  77. pcover
  78. etr_order(F,E,R,c,d)
  79. pcover F,E,R;
  80. pcube c,d;
  81. {
  82.     static int num_binary_vars;
  83.     int v,e0,e1;
  84.     int i,free_var;
  85.     pcube lastr,r;
  86.     int even_count,odd_count,free_count;
  87.     int odd,even;
  88.     VAR *p;
  89.  
  90.     num_binary_vars = cube.num_binary_vars;
  91.     c_free_list = (int *)calloc(num_binary_vars,sizeof(int));
  92.     r_free_list = (int *)calloc(num_binary_vars,sizeof(int));
  93.     reduced_c_free_list = (int *)calloc(num_binary_vars,sizeof(int));
  94.     unate_list = (VAR *)calloc(num_binary_vars,sizeof(VAR));
  95.     binate_list = (VAR *)calloc(num_binary_vars,sizeof(VAR));
  96.  
  97.     variable_order = (int *)calloc(num_binary_vars,sizeof(int));
  98.  
  99.     if(!c_free_list || !r_free_list || !reduced_c_free_list ||
  100.         !unate_list || !binate_list || !variable_order){
  101.         perror("etr_order:alloc");
  102.         exit(1);
  103.     }
  104.  
  105.     /* 1.Identify free variables of cube c */    
  106.     c_free_count = 0;
  107.     for(v = 0; v < num_binary_vars; v++){
  108.         e0 = v<<1;
  109.         e1 = e0 + 1;
  110.         if(is_in_set(d,e0) && is_in_set(d,e1)){
  111.             c_free_list[c_free_count++] = v;
  112.         }
  113.     }
  114.  
  115.     /* 2.Identify corresponding free variables of R */
  116.     r_head = 0;
  117.     r_free_count = 0;
  118.     reduced_c_free_count = 0;
  119.     for(i = 0; i < c_free_count; i++){
  120.         v = c_free_list[i];
  121.         e0 = v<<1;
  122.         e1 = e0 + 1;
  123.         free_var = TRUE;
  124.         foreach_set(R,lastr,r){
  125.             if(!is_in_set(r,e0) || !is_in_set(r,e1)){
  126.                 free_var = FALSE;
  127.                 break;
  128.             }
  129.         }
  130.         if(free_var){
  131.             r_free_list[r_free_count++] = v;
  132.         }
  133.         else{
  134.             reduced_c_free_list[reduced_c_free_count++] = v;
  135.         }
  136.     }
  137.  
  138.     /* 3.Identify unate and binate variables and sort them in the 
  139.          decreasing free_count */
  140.     unate_count = 0;
  141.     binate_count = 0;
  142.     for(i = 0; i < reduced_c_free_count; i++){
  143.         v = reduced_c_free_list[i];
  144.         e0 = v<<1;
  145.         e1 = e0 + 1;
  146.         even_count = 0;
  147.         odd_count = 0;
  148.         free_count = 0;
  149.         foreach_set(R,lastr,r){
  150.             odd = is_in_set(r,e0);
  151.             even = is_in_set(r,e1);
  152.             if(odd && even){
  153.                 free_count++;
  154.             }
  155.             else if(odd){
  156.                 odd_count++;
  157.             }
  158.             else{
  159.                 even_count++;
  160.             }
  161.         }
  162.         if(odd_count == 0 || even_count == 0){
  163.             p = &unate_list[unate_count++];
  164.             p->variable = v;
  165.             p->free_count = free_count;
  166.         }
  167.         else{
  168.             p = &binate_list[binate_count++];
  169.             p->variable = v;
  170.             p->free_count = free_count;
  171.         }
  172.     }
  173.  
  174.     qsort(unate_list,unate_count,sizeof(VAR),ascending);
  175.     qsort(binate_list,binate_count,sizeof(VAR),ascending);
  176.  
  177.     variable_head = 0;
  178.     variable_count = 0;
  179.     for(i = 0; i < binate_count; i++){
  180.         variable_order[variable_count++] = binate_list[i].variable;
  181.     }
  182.     for(i = 0; i < unate_count; i++){
  183.         variable_order[variable_count++] = unate_list[i].variable;
  184.     }
  185.     
  186.     /* 4.Recursively go down the tree defined by r_free_list,
  187.          invoking "etr" at the leaves */
  188.  
  189.     COVER = new_cover(10);
  190.     setup_bw(R,c);
  191.     SET(c,NONESSEN);
  192.  
  193.     aux_etr_order(F,E,R,c,d);
  194.  
  195.     free_bw();
  196.     free(c_free_list);
  197.     free(r_free_list);
  198.     free(reduced_c_free_list);
  199.     free(unate_list);
  200.     free(binate_list);
  201.     free(variable_order);
  202.  
  203.     return COVER;
  204. }
  205.  
  206. int
  207. ascending(p1,p2)
  208. VAR *p1,*p2;
  209. {
  210.     int f1 = p1->free_count;
  211.     int f2 = p2->free_count;
  212.  
  213.     if(f1 > f2){
  214.         return 1;
  215.     }
  216.     else if(f1 < f2){
  217.         return -1;
  218.     }
  219.     else{
  220.         return 0;
  221.     }    
  222. }
  223.  
  224. /*
  225.  * aux_etr_order
  226.  * Objective:main recursive routine for reducing the inessential signature cube.
  227.  *    Very similar to aux_ess_test_and_reduction;
  228.  * Input:
  229.  *    c: signature cube;
  230.  *    d: cube contained in the signature cube;
  231.  *    E: Extended don't care set. DC + identified ESC;
  232.  *    R: OFFSET cover;
  233.  */
  234. int
  235. aux_etr_order(F,E,R,c,d)
  236. pcover F,E,R;
  237. pcube c,d;
  238. {
  239.     pcover  minterms;
  240.     pcube d_minterm;
  241.     pcube sigma_d;
  242.     int v_index,e0,e1;
  243.     int i;
  244.     pcube *local_dc;
  245.  
  246.     /* Special Cases */
  247.     local_dc = cube3list(F,E,COVER);
  248.     if(cube_is_covered(local_dc,d)){
  249.         free_cubelist(local_dc);
  250.         return;
  251.     }
  252.     if(black_white() == FALSE){
  253.         free_cubelist(local_dc);
  254.         sigma_d = get_sigma(R,d);
  255.         sf_addset(COVER,sigma_d);
  256.         free_cube(sigma_d);
  257.         return;
  258.     }
  259.     if(variable_head == variable_count){
  260.         minterms = get_mins(d);
  261.         foreachi_set(minterms,i,d_minterm){
  262.             if(cube_is_covered(local_dc,d_minterm))continue;
  263.             sigma_d = get_sigma(R,d_minterm);
  264.             if(setp_equal(sigma_d,c)){
  265.                 RESET(c,NONESSEN);
  266.                 free_cube(sigma_d);
  267.                 break;
  268.             }
  269.             sf_addset(COVER,sigma_d);
  270.             free_cube(sigma_d);
  271.         }
  272.         sf_free(minterms);
  273.         free_cubelist(local_dc);
  274.         return;
  275.     }
  276.     else{
  277.         v_index = variable_order[variable_head];
  278.     }
  279.     free_cubelist(local_dc);
  280.         
  281.     e0 = (v_index<<1);
  282.     e1 = e0 + 1;
  283.  
  284.     variable_head++;
  285.  
  286.     set_remove(d,e1);
  287.     reset_black_list();
  288.     split_list(R,e0);
  289.     push_black_list();
  290.     S_EXECUTE(aux_etr_order(F,E,R,c,d),ETRAUX_TIME);
  291.     if(TESTP(c,NONESSEN) == FALSE)return;
  292.     pop_black_list();
  293.     merge_list();
  294.     set_insert(d,e1);
  295.  
  296.     set_remove(d,e0);
  297.     reset_black_list();
  298.     split_list(R,e1);
  299.     push_black_list();
  300.     S_EXECUTE(aux_etr_order(F,E,R,c,d),ETRAUX_TIME);
  301.     if(TESTP(c,NONESSEN) == FALSE)return;
  302.     pop_black_list();
  303.     merge_list();
  304.     set_insert(d,e0);
  305.  
  306.     variable_head--;
  307.  
  308.     return;
  309. }
  310.  
  311. pcover
  312. get_mins(c)
  313. pcube c;
  314. {
  315.     pcover minterms;
  316.     pcube d_minterm;
  317.     int i,j;
  318.  
  319.     minterms = new_cover(1);
  320.     d_minterm = new_cube();
  321.     set_copy(d_minterm,c);
  322.     set_and(d_minterm,d_minterm,cube.binary_mask);
  323.     for(i = cube.num_binary_vars;
  324.         i < cube.num_vars;i++){
  325.         for(j = cube.first_part[i]; j <= cube.last_part[i];j++){
  326.             if(is_in_set(c,j)){
  327.                 set_insert(d_minterm,j);
  328.                 sf_addset(minterms,d_minterm);
  329.                 set_remove(d_minterm,j);
  330.             }
  331.         }
  332.     }
  333.     free_cube(d_minterm);
  334.     return minterms;
  335. }
  336.  
  337. void print_list(int n,int *x,char *name)
  338. {
  339.     int i;
  340.     printf("%s:\n",name);
  341.     for(i = 0; i < n; i++){
  342.         printf("%d%c",x[i],(i+1)%10?'\t':'\n');
  343.     }
  344.     printf("\n");
  345. }
  346.